مسئله طولانی‌ترین مسیر
مسئله طولانی‌ترین مسیر (به انگلیسی: longest path problem) در تئوری گراف، مسئله یافتن یک مسیر ساده با با حداکثر طول در یک گراف خاص است.
مقدمه[ویرایش]
یک مسیر زمانی ساده نامیده می‌شود که دارای رئوس تکراری نباشد. بر خلاف مسئله کوتاهترین مسیر که کوتاهترین مسیر بین دو راس را به ما می‌دهد و در زمان چندجمله‌ای حل می‌شود، برای مسئله یافتن طولانی‌ترین مسیر زمان چندجمله‌ای وجود ندارد و جزء مسائل ان‌پی کامل(NP-complete)است. و به این معنی است که در زمان چندجمله‌ای نمی توان برای آن جواب پیدا کرد مگر اینکه P=NP باشد.
NP-completeness[ویرایش]
واضح است که اگر یک مسیر عمومی معین دارای مسیر Hamiltonian باشد، این مسیر Hamiltonian، بلندترین مسیر احتمالی است، زیرا همه رئوس احتمالی را طی می‌کند. برای حل مسئله Hamiltonian از یک الگوریتم طولانی‌ترین مسیر استفاده می‌کنیم، از این الگوریتم برای حل بلندترین مسیر در یک گراف با ورودی‌های یکسان و مجموعه k=|V|-۱ استفاده می‌کنیم که |V| تعداد رئوس در گراف است.
اگر یک مسیر Hamiltonian در گراف وجود داشته باشد پس الگوریتم yes را برمی گرداند، زیرا مسیر Hamiltonian دارای طول معادل با1-|V| است. بر عکس اگر الگوریتم دارای خروجی yes باشد، یک مسیر ساده با طول 1-|V| در گراف وجود دارد. و چون طول آن |V|-1 است می‌توان نتیجه گرفت که از همه رئوس گراف بدون تکرارگذشته‌است که همان مسیر Hamiltonian است. چون مسئله مسیر Hamiltonian یک مسئله ان پی کامل NP-complete است، این ساده‌سازی اثبات می‌کند که ان‌پی سخت (NP-hard) نیز است. برای اینکه تشان دهیم NP-complete است باید نشان دهیم NP است.
ارتباط با مسئله یافتن کوتاهترین مسیر[ویرایش]
مسئله یافتن طولانی‌ترین مسیر را می‌توان به مسئله یافتن کوتاهترین مسیر کاهش (reduction) داد.(گرچه ممکن است این گراف دارای دور با وزن منفی باشد) اگر گراف ورودی برای مسئله بلندترین مسیر G باشد، کوتاهترین مسیر ساده بر روی گراف Hamiltonian خواهد بود که دقیقاً مشابه G است، اما وزن‌های لبه منفی می‌شود، و بلندترین مسیر بر روی G است. هر چند هر یک از دورها با وزن مثبت در گراف اصلی G منتهی به دورهایی با وزن منفی در گراف Hamiltonian خواهد شد. بنابراین یافتن کوتاهترین مسیر ساده بر روی یک گراف با دورهایی با وزن منفی، نیز ان پی کاملاست. اگر G حاوی هیچ دوری نباشد، پس Hamiltonian هیچ دوری با وزن منفی نخواهد داشت و هر یک از الگوریتم‌های یافتن کوتاهترین مسیر اکنون می‌تواند بر روی Hamiltonian اجرا شوند تا مسئله اصلی در زمان چندجمله‌ای حل شود. بنابراین مسئله بلندترین مسیر بر روی گراف‌های بدون دور ساده‌است.
الگوریتم برای گراف‌های بدون دور[ویرایش]
همانطور که در بالا اشاره شد، مسئله یافتن طولانی‌ترین مسیر بر روی گراف‌های بدون دور را می‌توان در زمان چندجمله‌ای و از طریق منفی کردن وزن یال‌ها و اجرای یک الگوریتم یافتن کوتاهترین مسیر حل کرد.
راه حل برنامه‌نویسی پویا برای گراف‌های بدون دور[ویرایش]
همانطور که در بالا گفته شد طولانی‌ترین مسیر در گراف‌های بدون دور از طریق معکوس کردن وزن یال‌ها و اجرای الگوریتم‌های پیدا کردن کوتاهترین مسیر در زمان چندجمله‌ای حل کرد. الگوریتمی که در ادامه امده از روش تبدیل قبلی استفاده نمی‌کند و پیچیدگی زمانی بهتری هم دارد.
گراف‌های وزن دار جهت‌دار بی دور[ویرایش]
اگر G گراف جهت‌دار غیرمدور باشد، مسئلهٔ یافتن بلندترین مسیر را می‌توان در زمان خطی با استفاده از روشبرنامه نویسی پویا حل کرد. فرض کنید که (toporder(g دارای خروجی یک رشته از رأس‌ها در به صورت توپولوژیکی (که می‌تواند به وسیله یمرتب‌سازی توپولوژیکی انجام شود و این مرحله باید گراف جهت‌دار بدون دور باشد) باشد. بعلاوه، (V(G مجموعه رأس‌های گراف و (E(G مجموعه یال‌های گراف باشد، اگر گراف وزن دار بود وزن خود یال را به کار می‌بریم در غیر این صورت به هر یال یک وزن دلخواه به جز صفر اختصاص می‌دهیم. سپس الگوریتم زیر طول بلندترین مسیر را پیدا می‌کند.
algorithm dag-longest-path is
input:
Directed acyclic graph G
output:
Length of the longest path
length_to = array with |V(G)| elements of type int with default value 0
for each vertex v in topOrder(G) do
for each edge (v, w) in E(G) do
if length_to[w] <= length_to[v] + weight(G,(v,w)) then
length_to[w] = length_to[v] + weight(G, (v,w))
return max(length_to[v] for v in V(G))
مسئله‌های مشابه[ویرایش]
مطالعهٔ بیشتر[ویرایش]
منابع[ویرایش]
- مشارکت‌کنندگان ویکی‌پدیا. «Longest path problem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۴ ژوئیه ۲۰۱۲.